In DSP architectures that perform “in-place” fast Fourier transform (FFT) calculations, the results of the FFT are typically stored in memory in a non-consecutive order. For example, as shown in Table A below, an eight-point FFT having an initial array i of data elements numbered 0–7 will result in an output array j ordered as shown, with, for example, the results of the FFT calculation element 4 of array i being stored as the second element of array j.
TABLE Aij0014223641556377
Where a single memory space is used to store the results of in-place FFT calculations, such as in a Harvard or von Neumann architecture, a standard bit-reversing technique may be used to determine the position of a particular element in the memory space as follows. A binary index is used to represent each input element of an n-point FFT and each storage position in the memory space. The binary index is created of r digits where an n-point FFT is expressed as n=2r. Thus, an eight-point FFT will have a binary index of three digits as 8=23. As is shown in Table B below, the position of the results of an FFT calculation on an element in array i may be located in array j by bit-reversing the element's binary index. For example, the binary index of element 4 is 100 (410=1002). Bit reversing 100 results in a binary index of 001. Thus, the position of the result of an FFT calculation on element 4 in array i is located in array j at position 001.
TABLE BMemory/elementiindexj000001001. . .420102301164. . .1001510156110371117
Where more than one memory space is used to store the results of FFT calculations, such as in a modified Harvard architecture, standard bit-reversing techniques may not be used to determine the position of a particular element. Table C shows the positions of FFT input elements in arrays i1 and i2 as being stored in memory spaces X and Y respectively, while Table D shows the positions of the FFT results in arrays j1 and j2 being stored bit-reversed in memory spaces X and Y respectively. The binary index of element 3 is 011 (310=0112). Bit reversing 011 results in a binary index of 110. However, as each memory space X and Y contain only n/2 elements of an n-point FFT, the binary index of each memory space for an eight-point FFT only extends from 000 to 011. Thus, the position of the result of an FFT calculation on element 3 cannot be determined through standard bit reversing, as no memory position exists having a memory index of 110.
TABLE CMemory space XMemory space YMemory indexi1Memory indexi200000004001100150102010601130117
TABLE DMemory space XMemory space YMemory indexj1Memory indexj200000001001400150102010301160117
Prior art solutions to indexing in a modified Harvard DSP architecture include copying the FFT results from memory space Y to memory space X, thereby combining all FFT results into a single memory space that may be indexed using simple bit reversing. Unfortunately, this requires additional clock cycles to accomplish and also requires additional memory. Another prior art solution involves reading input from one memory space and writing the results to the other memory space. This, too, comes at the cost of additional memory overhead.
An indexing solution for use with a modified Harvard DSP architecture that requires less additional processing and memory overhead than prior art solutions would, therefore, be advantageous.